package com.aaron.leetcode.lc23;

import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.stream.Collectors;

/**
 * @author liurong
 * @date 2022/1/26 16:09
 * @version:
 */
//优先级队列（二叉堆）
public class Solution23_2 {
    int listsNum = 4;

    ListNode[] lists;

    {
        lists = new ListNode[listsNum];
        Random random = new Random();
        for (int index = 0; index < listsNum; index++) {
            List<ListNode> nodes = random.ints(random.ints(1, 1, 10).findFirst().getAsInt(), 0, 100).sorted().mapToObj(ListNode::new).collect(Collectors.toList());
            for (int i = 0; i < nodes.size() - 1; i++) {
                nodes.get(i).next = nodes.get(i + 1);
            }
            lists[index] = nodes.get(0);
        }


    }

    {
        lists = new ListNode[listsNum];
        List<List<Integer>> list = Arrays.asList(
                Arrays.asList(14, 17, 25, 29),
                Arrays.asList(5, 6, 37, 67, 73),
                Arrays.asList(24, 46, 48, 65, 79, 87),
                Arrays.asList(13, 28, 39));
        for (int i = 0; i < list.size(); i++) {
            ListNode node = new ListNode(list.get(i).get(0));
            lists[i] = node;
            for (int j = 1; j < list.get(i).size(); j++) {
                ListNode nextNode = new ListNode(list.get(i).get(j));
                node.next = nextNode;
                node = nextNode;
            }
        }
        System.out.println();

    }


    public ListNode mergeKLists(ListNode[] lists) {

        if (null == lists || 0 == lists.length) {
            //不能return new ListNode，否则过不了[]
            return null;
        }

        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, (a, b) -> (a.val - b.val));
        for (ListNode node : lists) {
            //不加下面的if，过不了[[]]用例
            //offer和add加null，直接抛空指针异常
            if (null==node){
                continue;
            }
            pq.add(node);
        }
        if (pq.size() == 0) {
            return null;
        }
        ListNode ans = pq.peek();
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();

            while (null!=pq.peek() && null!=node.next && pq.peek().val >= node.next.val) {
                node = node.next;
            }
            if (pq.peek() == null ) {
                continue;
            }
            if (node.next == null) {
                ListNode xx = pq.peek();//不要弹出，这一步是为了建立上个list最后一个node的next=null与下一个的联系，链接起来
                node.next = xx;
//                if (null != xx && null != xx.next) {
//                    pq.add(xx.next);
//                }
                continue;
            }

            pq.add(node.next);
            node.next = pq.peek();

        }
        return ans;
    }

    public static void main(String[] args) {
        Solution23_2 solution23_2 = new Solution23_2();
        ListNode ans = solution23_2.mergeKLists(solution23_2.lists);
        while (null != ans) {
            System.out.print(ans.val + " ");
            ans = ans.next;
        }
    }
}




